|
In the mathematical field of graph theory Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time as the determinant of a matrix derived from the graph. It is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph. Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a (0,1)-matrix with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise). For a given connected graph ''G'' with ''n'' labeled vertices, let ''λ''1, ''λ''2, ..., ''λn''−1 be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of ''G'' is : Equivalently the number of spanning trees is equal to ''any'' cofactor of the Laplacian matrix of ''G''. == An example using the matrix-tree theorem == First, construct the Laplacian matrix ''Q'' for the example kite graph ''G'' (see image at right): : Next, construct a matrix ''Q *'' by deleting any row and any column from ''Q''. For example, deleting row 1 and column 1 yields : Finally, take the determinant of ''Q *'' to obtain ''t(G)'', which is 8 for the kite graph. (Notice ''t(G)'' is the ''(1,1)''-cofactor of ''Q'' in this example.) 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kirchhoff's theorem」の詳細全文を読む スポンサード リンク
|